#ifndef _contest_eratosthenes_h_
#define _contest_eratosthenes_h_

#include<vector>
#include<assert.h>

using namespace std;

namespace contest
{
/**
 * Eratosthenes prime sive.
 **/
class eratosthenes
{
private:
    vector<bool> flag;
public:
    /**
     * @param size: The size of the sieve to do.
     **/
    eratosthenes(const size_t size):
             flag((size>>1) + 1, true)
    {
        const size_t half = (size>>1);
        for (size_t i=1; 2*i*(i+1)<=half; ++i)
            if (flag[i])
                for (size_t j=2*i*(i+1); j<=half; j+=(2*i+1))
                    flag[j] = false;
    }
    const bool operator [](const size_t n) const
    {
        if (n < 2)
            return false;
        if (n == 2)
            return true;
        if (n % 2 == 0)
            return false;
        return flag[n>>1];
    }
};

void test_eratosthenes()
{
    eratosthenes p(101);
    assert(p[1] == false);
    assert(p[2] == true);
    assert(p[3] == true);
    assert(p[4] == false);
    assert(p[5] == true);
    assert(p[6] == false);
    assert(p[7] == true);
    assert(p[8] == false);
    assert(p[9] == false);
    assert(p[10] == false);
    assert(p[11] == true);
    assert(p[101] == true);
}
}

#endif
